package arithmetic;

/**
 * @Author: Jie
 * @Date: 2019/3/11 14:19
 * @Function :338 比特位计数
 *
 * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 *
 * 示例 1:
 *
 * 输入: 2
 * 输出: [0,1,1]
 */
public class A_22_Binary_CountBits {

    public static void main(String[] args) {

    }

    /**
     * 方法2：递推，动态规划。
     *
     *  """
     *         1: 0001     3:  0011      0: 0000
     *         2: 0010     6:  0110      1: 0001
     *         4: 0100     12: 1100      2: 0010
     *         8: 1000     24: 11000     3: 0011
     *         16:10000    48: 110000    4: 0100
     *         32:100000   96: 1100000   5: 0101
     *
     *         由上可见：
     *         1、如果 i 为偶数，那么f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位，低位补零，所以1的数量不变。
     *         2、如果 i 为奇数，那么f(i) = f(i - 1) + 1， 因为如果i为奇数，那么 i - 1必定为偶数，
     *         而偶数的二进制最低位一定是0，
     *         那么该偶数 +1 后最低位变为1且不会进位，所以奇数比它上一个偶数bit上多一个1，即 f(i) = f(i - 1) + 1。
     *         :type num: int
     *         :rtype: List[int]
     *         """
     * @param num
     * @return
     */
    public static int[] countBits_01(int num) {
        int[] res = new int[num + 1];
        res[0] = 0;//初始值。
        //状态 i的 1个数。
        //状态转移。方程
        // f(i) = f(i - 1) + 1(判断奇偶)。
        for (int i = 1; i <= num; i++) {
            //1、如果 i 为偶数，那么f(i) = f(i/2)
            //2、如果 i 为奇数，那么f(i) = f(i - 1) + 1
            //+(i & 1) 奇数+1
            res[i] =  res[i >> 1] +(i & 1);//  (i & 1)判断奇偶   0b10010  ==  0b1001 + 最后一位的奇偶
        }
        return res;
    }

    //方法1 for循环 上一个类 hammingWeight
    public static int[] countBits(int num) {
        int[] res = new int [num+1];
        for (int i = 0; i <= num; i++) {
            res[i] = hammingWeight(i);
        }
        return res;
    }

    //二进制位 1的个数
    public static int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}
